package problem28_Implement_strStr;

import java.util.Arrays;

public class Solution {
	public int strStr(String haystack, String needle) {
		if(needle.length()==0)
			return 0;
		int[] next=getNext(needle);
		for(int i=0,j=0;i<haystack.length();i++){
			while(j!=0&&haystack.charAt(i)!=needle.charAt(j))
				j=next[j-1];
			if(haystack.charAt(i)==needle.charAt(j))
				j++;
			if(j==needle.length())
				return i-needle.length()+1;
		}
		return -1;
	}
	
	private int[] getNext(String target){
		int[] next=new int[target.length()];
		for(int i=1;i<target.length();i++){
			int k=next[i-1];
			while(k>0&&target.charAt(k)!=target.charAt(i))k=next[k-1];
			next[i] = target.charAt(k) == target.charAt(i) ? k+1 : k;
		}
		System.out.print(Arrays.toString(next));
		return next;
	}
	
	public static void main(String[] args){
		System.out.print("a".indexOf(""));
		System.out.println(new Solution().strStr("ABCDABCDABD","ABCDABD"));
	}
}
